package com.peng.leetcode.dynamic;

/**
 * DynamicMain
 * 动态规划
 *
 * @author: lupeng6
 * @create: 2020/12/29 15:44
 */
public class DynamicMain2 {

    public static void main(String[] args) {
        int[] goods = {2, 2, 4, 6, 3};
        int[] values = {3, 4, 8, 9, 6};
        int capacity = 9;
//        System.out.println(new Solution().maxValue(goods, values, capacity));
        System.out.println(new Solution1().maxValue(goods, values, capacity));
    }

    /**
     * 回溯法, 将所有的可能枚举, 计算最大重量
     *
     * @author lupeng6
     * @date 2020/12/29 16:08
     */
    static class Solution {
        // 最大价值
        private Integer maxValue = Integer.MIN_VALUE;

        // 物品重量
        private int[] goods;

        // 物品价值
        private int[] values;

        // 背包容量
        private int capacity;

        public int maxValue(int[] goods, int[] values, int capacity) {
            this.goods = goods;
            this.values = values;
            this.capacity = capacity;
            dfs(0, 0, 0);
            return maxValue;
        }

        public void dfs(int index, int currentValue, int currentWeight) {
            if (currentWeight == capacity || index == goods.length) {
                maxValue = Math.max(maxValue, currentValue);
                return;
            }
            // 不装
            dfs(index + 1, currentValue, currentWeight);
            // 装
            if (goods[index] + currentWeight <= capacity) {
                dfs(index + 1, currentValue + values[index], currentWeight + goods[index]);
            }
        }
    }

    /**
     * 动态规划
     *
     * @author lupeng6
     * @date 2020/12/29 18:47
     */
    static class Solution1 {
        // 物品重量
        private int[] goods;

        // 物品价值
        private int[] values;

        // 背包容量
        private int capacity;

        // 动态规划状态转移
        private int[][] states;

        public int maxValue(int[] goods, int[] values, int capacity) {
            this.goods = goods;
            this.values = values;
            this.capacity = capacity;
            this.states = new int[goods.length][capacity + 1];
            for (int i = 0; i < states.length; i++) {
                int[] state = states[i];
                for (int j = 0; j < state.length; j++) {
                    states[i][j] = -1;
                }
            }
            return dynamic();
        }

        private int dynamic() {
            states[0][0] = 0;
            if (goods[0] <= capacity) {
                states[0][goods[0]] = values[0];
            }
            for (int i = 1; i < goods.length; i++) {
                // 不装
                for (int j = 0; j <= capacity; j++) {
                    int prevRowValue = states[i - 1][j];
                    if (prevRowValue >= 0) {
                        states[i][j] = states[i - 1][j];
                    }
                }

                // 装
                for (int j = 0; j <= capacity - goods[i]; j++) {
                    int prevValue = states[i - 1][j];
                    int maxValue = prevValue + values[i];
                    int currentValue = states[i][j + goods[i]];
                    if (maxValue > currentValue && prevValue >= 0) {
                        states[i][j + goods[i]] = maxValue;
                    }
                }
            }

            int maxV = -1;
            int maxVIndex = -1;

            int[] lastRow = states[states.length - 1];
            for (int i = lastRow.length - 1; i >= 0; i--) {
                if (lastRow[i] > 0) {
                    maxV = lastRow[i];
                    maxVIndex = i;
                    break;
                }
            }

            // 输出选择的商品
            for (int i = states.length - 1; i >= 1; i--) {
                if (maxVIndex - goods[i] >= 0 && (states[i - 1][maxVIndex - goods[i]]) == (states[i][maxVIndex] - values[i])) {
                    System.out.println(i);
                    maxVIndex = maxVIndex - goods[i];
                }
            }
            if (maxVIndex != 0) {
                System.out.println(goods[0]);
            }

            return maxV;
        }
    }


}
